Definition

Let AβŠ†β„mA \subseteq \mathbb{R}^m be a bounded set of vectors. The Rademacher average of AA is

𝖱𝖺𝖽(A)=π”ΌΟƒβˆˆ{Β±1}m[supa∈A⁑σ⋅am]=π”ΌΟƒβˆˆ{Β±1}m[supa∈A⁑1mβˆ‘i=1mΟƒiai]\mathsf{Rad}(A) = \mathbb{E}_{\sigma \in \{\pm 1 \}^m} \left[ \sup_{a \in A} \frac{\sigma \cdot a}{m} \right] = \mathbb{E}_{\sigma \in \{\pm 1 \}^m} \left[ \sup_{a \in A} \frac{1}{m} \sum_{i=1}^m \sigma_i a_i \right]

where Οƒi∼i.i.d.unif⁑{βˆ’1,1}\sigma_i \overset{\text{i.i.d.}}{\sim} \operatorname{unif}\{-1,1\} (Rademacher random variable).

Fix mβˆˆβ„•m \in \mathbb{N}, let 𝒳\mathcal{X} be a nonempty set, and suppose class of functions β„±:𝒳→[βˆ’1,1]\mathcal{F}: \mathcal{X} \to [-1,1]. For any set S=(x1,...,xm)βˆˆπ’³mS = (x_1,...,x_m) \in \mathcal{X}^m, let

β„±(S)={(f(x1),...,f(xm)):fβˆˆβ„±}βŠ†β„m\mathcal{F}(S) = \{(f(x_1),...,f(x_m)): f \in \mathcal{F}\} \subseteq \mathbb{R}^m

Fix sample Sβˆˆπ’³mS \in \mathcal{X}^m, then the empirical Rademacher complexity of β„±\mathcal{F} with respect to SS is

𝖱𝖺𝖽S(β„±)=𝖱𝖺𝖽(β„±(S))=π”ΌΟƒβˆˆ{Β±1}m[supfβˆˆβ„±β‘1mβˆ‘i=1mΟƒif(xi)]\mathsf{Rad}_S(\mathcal{F}) = \mathsf{Rad}(\mathcal{F}(S)) = \mathbb{E}_{\sigma \in \{\pm 1 \}^m} \left[ \sup_{f \in \mathcal{F}} \frac{1}{m} \sum_{i=1}^m \sigma_i f(x_i) \right]

Let π’Ÿ\mathcal{D} be a distribution over 𝒳\mathcal{X}, then the Rademacher complexity of size mm of β„±\mathcal{F} with respect to π’Ÿ\mathcal{D} is

Notes

See also

References

  1. J. Shafer, Class Lecture, Topic: "Unit 6: Rademacher Complexity." CS 294-220, UC Berkeley, Spring 2021. https://piazza.com/class_profile/get_resource/khs64r6r5yn154/km1at8uo4o3mk
  2. C. Scott, Class Lecture, Topic: "10: Rademacher Complexity." EECS 598, University of Michigan, Winter 2014. https://web.eecs.umich.edu/~cscott/past_courses/eecs598w14/notes/10_rademacher.pdf
  3. https://people.math.binghamton.edu/qiao/math605/book/rademacher-complexity.html
  4. https://www.cs.cmu.edu/~ninamf/ML11/lect1117.pdf
  5. J. Kuck, A. Sabharwal, and S. Ermon, β€œApproximate Inference via Weighted Rademacher Complexity,” Jan. 27, 2018,Β arXiv: arXiv:1801.09028. doi: 10.48550/arXiv.1801.09028.